package wh.两两交换链表中的节点;

/**
 * @author: wh(1835734390 @ qq.com)
 * @date: 2022/11/24 16:55
 * @description:两两交换链表中的节点，只能改变指针，不能改变值 没有头节点，第一个节点为首节点
 * @version:
 */
public class Solution {
    public static void main(String[] args) {
        ListNode listNode = new ListNode(1,new ListNode(2,new ListNode(3,new ListNode(4))));
        ListNode listNode2 = new ListNode(null,new ListNode(1,new ListNode(2,new ListNode(3,new ListNode(4,new ListNode(8))))));
     //   swapPairs2(listNode2);
        swapPairs(listNode);
    }


    //带头节点的版本
    public static ListNode swapPairs2(ListNode head) {
        ListNode pre = new ListNode(0);
        pre.next = head;
        ListNode p = head.next;
        ListNode r = head;
        r.next = null;
        while (p != null && p.next != null){
            //1 先采用尾插法把奇数节点进行插入
            r.next = p;
            //建立一个哨兵prer 表示尾节点的前驱
            ListNode prer = r;
            r = r.next;
            p = p.next;
            //2 采用首插法把偶数节点插入到尾节点之前
            ListNode q = p.next;
            p.next = prer.next;
            prer.next = p;
            p = q;
        }
        return head;
    }
    //不带头节点的版本
    public static ListNode swapPairs(ListNode head) {
        if (head == null || head.next == null){
            return head;
        }
        //先把前两个进行了一个交换
        ListNode p = head.next;
        head.next = p.next;
        p.next = head;
        head = p;
        ListNode r = head.next;
        ListNode q = r.next;
        while (q != null && q.next != null){
            //采用头插法把q.next插入到r和q之间
            ListNode m = q.next;
            ListNode n = m.next;
            m.next = q;
            r.next = m;
            q.next = n;
            r = q;
        }
        System.out.println(head);
        return head;
    }

    public ListNode swapPairs3(ListNode head) {
        ListNode pre = new ListNode(0);
        pre.next = head;
        ListNode temp = pre;
        while(temp.next != null && temp.next.next != null) {
            ListNode start = temp.next;
            ListNode end = temp.next.next;
            //把temp.next指向temp.next.next
            temp.next = end;
            //头插法
            start.next = end.next;
            end.next = start;
            //为下一轮循环做准备
            temp = start;
        }
        return pre.next;
    }

    //递归解法

    public ListNode swapPairs4(ListNode head) {
        if (head == null || head.next == null)
            return head;
        ListNode rest = head.next.next;
        ListNode newHead = head.next;
        newHead.next = head;
        head.next = swapPairs4(rest);
        return newHead;
    }





}
